package cn.com.caluation;

/*
*
* 二分查找
* 前提 数据已经排序好了
*
* 取长度的中间值
* 取中间值与查找值比较
* 大于查找值就靠比查找值小的找
*小于就靠查找值大的找
* */
public class binarySearch {
    /*
    * 希尔排序
    * 先制造间隙分组 n/2 或 n/4
    * 对组内元素进行插入排序
    * 直到间隙为1
    *
    * 将较大的数值先移动到后方
    * */
    public static int[] shell(int[] a){
        int n = a.length;
        for(int gap = n/2; gap >0 ; gap /=2){

            for(int i = gap; i < n;i++){
                int t = a[i];
                int j = i;
                //与上一个间隙的组进行插入排序
                while (j>=gap){
                    if(t < a[j - gap]){
                        a[j] = a[j - gap];
                        j-=gap;
                    }else {
                        break;
                    }
                }

                a[j] = t;
            }
        }

        return a;
    }

    /*
    * 插入排序,稳定排序
    * 将数组分为两个区域,未排序区和已经排序区,每一伦从未排序区中抽出一个数字,插入到排序区中,做顺序处理
    * 取出未排序数字的一个数,与排序区做比较,若比排序区的数字小,比较的排序区数字退一位
    * */
    public static int[] insertSort(int[] a){

        for(int i = 1; i < a.length;i++){
            int t = a[i];
            int j = i;
            while (j >=1){
                if(t < a[j-1]){
                    a[j] = a[j - 1];
                    j--;
                }else {
                    break;
                }
            }
            a[j] = t;
        }

        return a;
    }

    /*
    选择排序
    * 排序子集,将数据分成两个部分,排序好的和未排序好的,将未排序好的放入排序子集
    * 重复以上步骤,实现数据有序
    *
    * */
    public static int[] sortSelect(int[] a){

        for(int i=0;i < a.length;i++){
            int tmp;
            for(int s = i + 1;s < a.length;s++){
                if(a[i] > a[s]){
                    tmp = a[i];
                    a[i] = a[s];
                    a[s] = tmp;
                }
            }
        }
        return a;
    }


    public static int search(int[] a,int t){
        int l = 0,r=a.length-1,m;

        int count = 0;
        while (r >= l) {
            count++;
            m = (l + r)/2;
            if (a[m] == t) {
                System.out.println("查找次数: " + count);
                return m;
            } else if (a[m] > t) {
                r = m - 1;
            } else if (a[m] < t) {
                l = m + 1;
            }
        }

        return -1;
    }
    /*
    * 冒泡排序
    *
    * */
    public static int[] BubbleSort(int[] a){

        for(int i = 0; i < a.length;i++){
            int tmp;
            for(int j = 0; j < a.length - i;j++){
                if(a[j] > a[j+1]){
//                    tmp = a[j + 1];
//                    a[j + 1] = a[j];
//                    a[j] = tmp;
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] =tmp;
                }
            }

        }


        return a;
    }

    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int[] array2 = {1,4,6,7,15,33,39,50,64,78,75,81,89,96};
        int[] array3 = {1,4,6,7,15,33,39,1,5,8,11,19};
        int[] array4 = {1,6,10,5,8};

        shell(array3);
        insertSort(array4);
        sortSelect(array3);
        System.out.println(array.length + "," + array2.length);
//        array = BubbleSort(array);
        System.out.println(search(array,48));
        System.out.println(search(array2,81));

    }
}
